package pack;

public class BinaryTree
{
	public class Node
	{
		int num;
		Node left;
		Node right;
		Node iam;
		Node parent;
		
		public Node(int num, Node parent)
		{
			this.num = num;
			this.left = null;
			this.right = null;
			this.iam = this;
			this.parent = parent;
		}
	}
	
	Node root;
	int lenght;
	
	public BinaryTree()
	{
		root = null;
		lenght = 0;		
	}
	
	public BinaryTree(int num)
	{
		root = new Node(num, null);
		lenght = 1;
	}

	public Node insert(int num)
	{
		lenght++;
		if(root == null)
		{
			root = new Node(num, null);
			return root; 
		}
		
		Node node = root;
		while(node != null)
			if(num >= node.num)
				if(node.right == null)
				{
					node.right = new Node(num, node);
					return node.right;
				}
				else
					node = node.right;
			else if(num < node.num)
				if(node.left == null)
				{
					node.left = new Node(num, node);
					return node.left;
				}
				else
					node = node.left;
		
		lenght--;
		return null;
	}
	
	public void printTree()
	{
		System.out.println("\nLenght: " + lenght);
		printTree(root, 0);
	}
	
	private void printTree(Node node, int level)
	{
		 if(node.right != null)
			 printTree(node.right, level+1);
		 
		 for(int k = 0; k < level; k++)
			 System.out.print("\t");
		 System.out.println(node.num);
		 
		 if(node.left != null)
			 printTree(node.left, level+1);
	}
	
	public Node search(int num)
	{
		Node minNode = root;
		Node maxNode = root;
		
		Node node = root;
		while(node != null)
			if(num == node.num)
				return node;
			else if(num > node.num)
			{
				if(maxNode.num < node.num)
					maxNode = node;
				minNode = node;
				node = node.right;
			}
			else if(num < node.num)
			{
				if(minNode.num > node.num)
					minNode = node;
				maxNode = node;
				node = node.left;
			}
		
		if(maxNode.num - num <= num - minNode.num)
			return maxNode;
		else
			return minNode;
	}

	public Node getMax()
	{
		Node node = root;
		while(node.right != null)
			node = node.right;
		return node;
	}
		
	public Node getMin()
	{
		Node node = root;
		while(node.left != null)
			node = node.left;
		return node;
	}

	public boolean remove(int num)
	{
		return remove(num, root);
	}
	
	private boolean remove(int num, Node node)
	{
		while(node != null)
		{
			if(num < node.num)
				node = node.left;
			else if(num > node.num)
				node = node.right;
			else if(num == node.num)
			{
				if(node.left != null && node.right != null)
				{
					if(node.right.left == null)
					{
						node.right.left = node.left;
						
						if(node == root)
							root = node.right;
						else if(node.parent.left == node)
							node.parent.left = node.right;
						else if(node.parent.right == node)
							node.parent.right = node.right;
						lenght--;
						return true;
					}
					else
					{
						Node nodeLeft = node.right.left;
						while(nodeLeft.left != null)
							nodeLeft = nodeLeft.left;
						node.num = nodeLeft.num;
						return remove(nodeLeft.num, nodeLeft);
					}
				}
				else	
				{
					if(node.left == null && node.right == null)
					{
						if(node == root)
							root = null;
						else if(node.parent.left == node)
							node.parent.left = null;
						else if(node.parent.right == node)
							node.parent.right = null;
					}
					else if(node.left != null)
					{
						if(node == root)
							root = node.left;
						else if(node.parent.left == node)
							node.parent.left = node.left;
						else if(node.parent.right == node)
							node.parent.right = node.left;
					}
					else if(node.right != null)
					{
						if(node == root)
							root = node.right;
						else if(node.parent.left == node)
							node.parent.left = node.right;
						else if(node.parent.right == node)
							node.parent.right = node.right;
					}
					lenght--;
					return true;
				}
			}
		}
		return false;
	}
	
	public static void main(String[] args)
	{
		BinaryTree tree = new BinaryTree();
		
		int amount = 5;
		for(int k = 0; k < amount; k++)
		{
			int number = (int) (Math.random()*amount*2-amount);
			System.out.print(number + ",");
			tree.insert(number);
		}
		
		tree.printTree();
		System.out.println("Remove: " + 4 + " : " + tree.remove(4));

		int search = (int) (Math.random()*amount*2-amount);
		int searchNum = tree.search(search).num;
		System.out.println("Search: " + search);
		System.out.println("Search Num: " + searchNum);
		System.out.println("Remove: " + searchNum + " : " + tree.remove(searchNum));
		System.out.println("Remove: " + searchNum/2 + " : " + tree.remove(searchNum/2));
		System.out.println("Min: " + tree.getMin());
		System.out.println("Max: " + tree.getMax());
		
		tree.printTree();
	}
}
